#include<bits/stdc++.h>
using namespace std;
#define maxsize 10

typedef struct treeNode
{
    char data;
    struct treeNode* Lchild;
    struct treeNode* Rchild;
}tree,*LPtree;


LPtree initTree(char data)
{
    LPtree newNode = (LPtree)malloc(sizeof(tree));
    newNode->data = data;
    newNode->Lchild=NULL;
    newNode->Rchild=NULL;
    return newNode;
}

void insertChildNode(LPtree pNode,LPtree LNode,LPtree RNode)
{
    pNode->Lchild = LNode;
    pNode->Rchild = RNode;
}

void printNowNode(LPtree now)
{
    printf("%c ",now->data);
}

void prePrintAllNode(LPtree root)
{
    if(root!=NULL)
    {
        printNowNode(root);
        prePrintAllNode(root->Lchild);
        prePrintAllNode(root->Rchild);
    }
}

void midPrintAllNode(LPtree root)
{
    if(root!=NULL)
    {
        midPrintAllNode(root->Lchild);
        printNowNode(root);
        midPrintAllNode(root->Rchild);
    }
}

void endPrintAllNode(LPtree root)
{
    if(root!=NULL)
    {
        endPrintAllNode(root->Lchild);
        endPrintAllNode(root->Rchild);
        printNowNode(root);        
    }
}

void printpretree(LPtree root)//根左右
{
    if(root==NULL)
        return;

    LPtree stack[maxsize];//用栈存储每次打印节点的位置和值
    int stackTop = -1;//栈顶标记
    LPtree pMove = root;
    while(stackTop!=-1||pMove)
    {
        while(pMove)
        {
            printf("%c ",pMove->data);
            stack[++stackTop]= pMove;
            pMove = pMove->Lchild;
        }
        if(stackTop!=-1)
        {
            pMove = stack[stackTop];
            stackTop--;
            pMove = pMove->Rchild;
        }
    }
}

void printmidtree(LPtree root)//左 根 右
{
    if(root==NULL)
        return;
    LPtree pMove = root;
    LPtree stack[maxsize];
    int stackTop=-1;
    while(stackTop!=-1||pMove)
    {
        while(pMove)
        {
            stack[++stackTop] = pMove;
            pMove = pMove->Lchild;
        }
        if(stackTop!=-1)
        {
            pMove = stack[stackTop];
            stackTop--;
            printf("%c ",pMove->data);
            pMove = pMove->Rchild;
        }
    }
}

void printendtree(LPtree root)//左 右 根
{
    if(root==NULL)
        return;
    LPtree stack[maxsize];
    int stackTop = -1;
    LPtree pMove = root;
    LPtree pLast = NULL;
    while(pMove)
    {
        stack[++stackTop] = pMove;
        pMove = pMove->Lchild;
    }
    while(stackTop!=-1)
    {
        pMove = stack[stackTop--];
        if(pMove->Rchild==NULL||pMove->Rchild==pLast)//判断右子树是否存在或者是否已经访问
        {
            printf("%c ",pMove->data);
            pLast = pMove;//更新当前子树
        }
        else
        {
            pMove = stack[++stackTop];
            pMove = pMove->Rchild;
            while(pMove)
            {
                stack[++stackTop] = pMove;
                pMove = pMove->Lchild;
            }
        }
    }
}

int main()
{
    LPtree A = initTree('A');
    LPtree B = initTree('B');
    LPtree C = initTree('C');
    LPtree D = initTree('D');
    LPtree E = initTree('E');
    LPtree F = initTree('F');
    LPtree G = initTree('G');
    insertChildNode(A,B,C);
    insertChildNode(B,D,NULL);
    insertChildNode(D,NULL,G);
    insertChildNode(C,E,F);
    //prePrintAllNode(A);
    //midPrintAllNode(A);
    //endPrintAllNode(A);
    printendtree(A);
}